易于使用的计算机

虚拟化

虚拟化可以分成两部分

虚拟化CPU

目标

让用户觉得自己的单核CPU电脑能够同时运行多个程序

Mechanism

进程切换

进程调度

在进程切换的时候,OS应该选择哪一个进程占用CPU才是合理且高效的呢?

Policies

First In, First Out (FIFO)

Shortest Job First (SJF)

Shortest Time-to-Completion First (STCF)

Round Robin(RR)

多级反馈队列

多级反馈队列是一种实际运用相对较多的调度算法,在Windows NT内核中都有用到,我们单独拿出来讲

虚拟化内存

目标

Mechanism

Policies

并发

  • 并行队列
    • 不像单链表只能从表头开始操作,队列可以从队头和队尾同时进行操作,所以我们可以对对头和队尾分别加锁
    • Alt text
    • 注意这份代码中使用了一个哨兵节点,这也是我们在实现普通队列的时候应该做的(还记得判断队列为空还是为满的条件吗?)
  • 并行哈希表
    • Alt text
    • 使用前面建立的并行链表,我们就能实现一个非常高效的并行哈希表
    • 当然使用的是开放式冲突解决策略中的独立链表法
  • 使用同步原语解决一些问题

    • 生产者/消费者问题
      • 下面这份代码只能支持单线程运行producer和consumer函数
        • Alt text
      • 下面这份代码才是真正的多线程解决方案
        • Alt text
    • 读者/写者问题
      • 使用基本的lock和condition variable
        • 我们需要一个numReaders变量,记录当前读者的个数,通过这个变量的值来使用条件变量,然后还需要一个lock,用来互斥访问numReaders
      • 使用信号量
        • Alt text
    • 哲学家就餐问题
      • Alt text
      • 打破死循环
        • Alt text
  • event-based concurrency
    • 暂时没看
  • Common Concurrency Problems
    • 暂时没看
  • 持久化

    I/O设备

    Interlude: File and Directories

    file

    directories

    怎么组织同一个目录下的文件或者子目录?
    现代操作系统一般使用B树。

    对于目录和纯文件来说,二者存储的信息有什么区别?
    纯文件,存储的是文件的内容,对于目录,存储的是目录下的子目录和文件以及它们对应的inode number。

    Very Simple File System(VSFS)

    Locality and The Fast File System

    VSFS的效率太低了,我们需要更加快速的操作系统,Fast File System (FFS)。